package org.example;

import java.util.HashMap;
import java.util.Map;

public class Test2 {
    //leetcodde 两数之和 II - 输入有序数组 https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/?envType=study-plan-v2&envId=top-interview-150

    /**
     * hash记录已经遍历的元素和下标
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum1(int[] numbers, int target) {
        int[] ret = new int[2];
        Map<Integer,Integer> hash = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            Integer tmp = hash.get(numbers[i]);
            if (tmp == null) {
                hash.put(target-numbers[i],i);
            }else {
                ret[0] = tmp + 1;
                ret[1] = i + 1;
            }
        }
        return ret;
    }

    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        int[] ret = new int[2];
        while (left < right) {
            while (left < right && numbers[left] + numbers[right] > target) right--;
            while (left < right && numbers[left] + numbers[right] < target) left++;
            if (numbers[left] + numbers[right] == target) {
                ret[0] = left + 1;
                ret[1] = right + 1;
                return ret;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        int[] arr = {2,7,11,15};
        test2.twoSum(arr,9);
    }
}
